package vip.zhenzicheng.algorithm.leetcode.binary_search;

/**
 * <a href="https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/">寻找旋转排序数组中的最小值 [中等]</a>
 *
 * @author zhenzicheng
 * @date 2022-07-18 09:46
 */
public class FindMinimumInRotatedSortedArray_153 {

  public int findMin(int[] nums) {
    if (nums.length == 1) {
      return nums[0];
    }

    int start = 0, end = nums.length - 1;
    while (start <= end) {
      if (start + 1 == end) { // 只间隔一个元素则直接比较
        return Math.min(nums[start], nums[end]);
      }

      int mid = (start + end) / 2;
      if (nums[start] <= nums[mid] && nums[mid] <= nums[end]) { // 左边的就是最小
        return nums[start];
      }
      // 中间mid对应的最小说明最小值一定在mid左边或者刚好在mid的位置
      else if (nums[start] >= nums[mid] && nums[mid] < nums[end]) {
        end = mid;
      }
      // 最小值在mid右边
      else {
        start = mid;
      }
    }
    return -1;
  }
}
